import java.util.HashMap;

/**
 * @author VernHe
 * @date 2021年06月12日 10:43
 */
public class Solution_0160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (null == headA || null == headB) {
            return null;
        }
        HashMap<ListNode, ListNode> map = new HashMap<>();

        ListNode node = headA;
        // 初始化set
        while (null != node) {
            System.out.println(node.val + "放入");
            map.put(node,node.next);
            node = node.next;
        }

        // 查找第一个交点
        node = headB;
        while (null != node) {
            if (map.containsKey(node)) {
                return node;
            }
            System.out.println(node.val + "不在map中");
            node = node.next;
        }
        return null;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (null == headA || null == headB) {
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}
